package sword;

/**
 * 问题：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
 * (动态规划)
 *
 * @author longzj
 */
public class JumpFloor {

    public static void main(String[] args) {
        JumpFloor floor = new JumpFloor();
        int result = floor.jumpFloorII(4);
    }

    private int jumpFloorII(int target) {

        int[] values = new int[target];
        values[0] = 1;
        return jumpFloorInternal(target - 1, values);
    }

    /**
     * 正如题目所言，假设我们需要跳5个台阶，会出现这样的情况：<br>
     * 1.第一次跳1步时,其余4步有多少种跳法？<br>
     * 2.第一次跳2步时，其余3步有多少种跳法？<br>
     * 3. .....<br>
     * 那在1的基础上再跳1步，其余3步有多少种跳法？这样就3步的跳法已经在2中体现，故我们在每一次跳的时候，可以存储下对应步数的
     * 跳法，后面的跳法数不用再递归计算，最后的跳法结果，就等于每种步数选择的总和。
     *
     * @param target 具体的楼梯数
     * @param values 存放跳法的数组
     * @return 跳法数
     */
    private int jumpFloorInternal(int target, int[] values) {
        int result = values[target];
        if (result != 0) {
            return result;
        }
        for (int count = 0; count < target; count++) {
            result += jumpFloorInternal(count, values);
        }
        result += 1;
        values[target] = result;
        return result;
    }
}
